package sort

// 归并排序
func mergeSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	half := len(arr) / 2
	left := arr[0:half]
	right := arr[half:]
	return merge(mergeSort(left), mergeSort(right))
}

func merge(left, right []int) []int {
	var result []int
	for len(left) != 0 && len(right) != 0 {
		if left[0] > right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	if len(left) > 0 {
		result = append(result, left...)

	}
	if len(right) > 0 {
		result = append(result, right...)
	}
	return result
}
